package Queue_and_Stack;

/*
每日温度
给定一个整数数组temperatures，表示每天的温度，返回一个数组answer，其中answer[i]是指对于第 i 天，下一个更高温度出现在几天后。
如果气温在这之后都不会升高，请在该位置用0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出:[1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出:[1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/queue-stack/genw3/
 */

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class _33每日温度 {
    public static void main(String[] args) {

        int[] arr = {73,74,75,71,69,72,76,73};
        int[] res = dailyTemperatures2(arr);
        for (int re : res) {
            System.out.print(re + " ");
        }

    }

    //暴力
    //超时
    public static int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        res[n - 1] = 0;
        for (int i = 0; i < n - 1; i++) {
            int day = 1;
            for (int j = 1 + i; j < n; j++) {
                if(temperatures[j] <= temperatures[i]) {
                    day++;
                }else {
                    res[i] = day;
                    break;
                }
            }
        }
        return res;
    }

    //单调栈  O(n)  O(n)
    public static int[] dailyTemperatures2(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
//        Stack<Integer> stack = new Stack<>();   效率太慢   160ms   JDK1.0的产物现在已经不推荐使用了
        Deque<Integer> stack = new LinkedList<>();  // 26ms    Deque是双端队列，是一个具有栈和队列的数据结构
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int pop = stack.pop();
                res[pop] = i - pop;
            }
            stack.push(i);
        }
        return res;
    }

    //官解：单调栈
    class Solution {
        public int[] dailyTemperatures(int[] temperatures) {
            int length = temperatures.length;
            int[] ans = new int[length];
            Deque<Integer> stack = new LinkedList<Integer>();
            for (int i = 0; i < length; i++) {
                int temperature = temperatures[i];
                while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                    int prevIndex = stack.pop();
                    ans[prevIndex] = i - prevIndex;
                }
                stack.push(i);
            }
            return ans;
        }
    }

}
